﻿using System;
using System.Collections.Generic;

namespace Bouyei.Algo.Graph
{
    /// <summary>
    /// douglas抽稀算法
    /// </summary>
    public class DouglasAlgorithm
    {
        public List<DougNode> Nodes { get; private set; }
        public double Tolerance { get; private set; }

        public DouglasAlgorithm(List<DougNode> Nodes, double Tolarence)
        {
            this.Nodes = Nodes;
            this.Tolerance = Tolarence;
        }

        public List<DougNode> Execute()
        {
            SimplifyTo(0, Nodes.Count - 1);

            return Nodes.FindAll(x => x.Flag == 0);
        }

        private void SimplifyTo(int sIndex, int eIndex)
        {
            if (eIndex == sIndex + 1) return;

            DougNode from = Nodes[sIndex], to = Nodes[eIndex];

            //var sqrt = Math.Sqrt(Math.Pow(from.Y - to.Y, 2) + Math.Pow(from.X - to.X, 2));
            var x_dist = (to.X - from.X);//方向很重要
            var y_dist = (from.Y - to.Y);//方向很重要
            var xy_dist = ((from.X * to.Y) - (to.X * from.Y));

            var xysqrt = Math.Sqrt(Math.Pow(x_dist, 2) + Math.Pow(y_dist, 2));

            double max = 0;
            int maxIndex = sIndex;

            //计算点到指定线段的最大距离
            for (int i = sIndex + 1; i < eIndex; ++i)
            {
                var dist = Nodes[i].Distance(x_dist, y_dist, xy_dist, xysqrt);
                if (dist > max)
                {
                    max = dist;
                    maxIndex = i;
                }
            }

            //删除该范围点
            if (max <= Tolerance)
            {
                for (int i = sIndex + 1; i < eIndex; ++i)
                {
                    Nodes[i].Flag = -1;
                }
            }
            else
            {
                SimplifyTo(sIndex, maxIndex);
                SimplifyTo(maxIndex, eIndex);
            }
        }
    }

    public class DougNode
    {
        public double X { get; set; }

        public double Y { get; set; }

        public int Flag { get; set; }

        public DougNode(double X, double Y)
        {
            this.X = X;
            this.Y = Y;
        }
        public bool Equal(DougNode point)
        {
            return this.X == point.X && this.Y == point.Y;
        }

        public double Distance(double x_dist, double y_dist, double xy_dist,
            double xysqrt)
        {
            var dist = Math.Abs(x_dist * Y + y_dist * X + xy_dist) / xysqrt;

            return dist;
        }
    }
}
